1. Field of the Invention
The present invention relates generally to computer graphics.
2. Background Art
Computer graphics systems render all kinds of objects for display and animation. An object is modeled in object space by a set of primitives (also called graphics primitives). Examples of primitives include, but are not limited to, triangles, polygons, lines, tetrahedra, curved surface, and bit-map images. Each primitive includes one or more vertices that define the primitive (or a fragment) in terms of position, color, depth, texture, and/or other information helpful for rendering.
Rendering terrain data has become especially important in many applications, such as, flight simulation and gaming. Terrain elevation is often defined by height data. Any type of height data can be used. For example, a height field can be defined by a function, h(x, y), where (x, y) forms a 2-D domain and the height function h represent elevation. In one example, the height function is often modeled or sampled on a uniform grid in the domain. The samples are then stored as a digital elevation map (DEM) that is essentially a gray-scale image representative of height.
Visibility culling on a height field involves the detection of height field portions (e.g., tiles) and features (e.g., buildings) that cannot be seen from a particular viewpoint. There have been many visibility algorithms proposed for general scenes and models. See, e.g., Seth J. Teller and Carlo H. Séquin, “Visibility Preprocessing for Interactive Walkthroughs,” Computer Graphics (Proceedings of SIGGRAPH 91), 25 (4), pp. 61-69, July 1991; Ned Greene and M. Kass, “Hierarchical Z-Buffer Visibility,” Proceedings of SIGGRAPH93, Computer Graphics Proceedings, Annual Conference Series, pp. 231-240 (1993, Anaheim, Calif.); and Hansong Zhang, D. Manocha, T. Hudson and K. Hoff, “Visibility Culling Using Hierarchical Occlusion Maps,” Proceedings of SIGGRAPH97, Computer Graphics Proceedings, Annual Conference Series, pp. 77-88, August 1997. These alogrithms can be applied to terrain data, but do not take advantage of the characteristics of terrain data. Other algorithms have been proposed that directly involve terrain data. One approach by Max computes horizons at points on a bump map (one application of a height field). The result is used to compute shadows on bump mapped surfaces. The horizon is detected in eight directions around each sample point. Points that do not fall directly in these directions are not considered. See, Nelson L. Max, “Shadows for Bump-Mapped Surfaces,” Advanced Computer Graphics (Proceedings of Computer Graphics Tokyo '86), Tsiyasu L. Kunii, Ed. 1986, pp. 145-156, Springer-Verlag; and Nelson L. Max, “Horizon Mapping: Shadows for Bump-Mapped Surfaces”, The Visual Computer, vol. 4, no. 2, pp. 109-117, July 1988. A similar algorithm is applied to triangulated terrain and processes 24 directions around each point; the result is used to compute bi-directional reflection functions. See, B. Cabral, N. L. Max, and R. Springmeyer, “Bidirectional Reflection Function from Surface Bump Maps”, in Computer Graphics (SIGGRAPH '87 Proceedings), July 1987, vol. 21, pp. 273-281. These algorithm can be adapted to visibility applications but are limited. To avoid visual artifacts, the number of directions they consider has to be increased greatly.
For more accurate horizons, an approach by Stewart considers all points of the terrain rather than only those that lie in particular directions. See, A. James Stewart, “Fast Horizon Computation at All Points of a Terrain With Visibility and Shading Applications,” IEEE Transactions on Visualization and Computer Graphics, 4(1), pp. 82-93. Another approach shows that, when the terrain is stored as a dense grid of n rectilinear prisms, one needs to consider O(square root(n)) directions to avoid under-sampling. See, Daniel Cohen-Or and Amit Shaked, “Visibility and Dead-Zones in Digital Terrain Maps,” Computer Graphics Forum, 14(3), Blackwell Publishers: Edited by Frits Post and Martin Göbel, pp. 171-180. See, also, a similar algorithm using ray tracing. C-H. Lee and Y. G. Shin, “An Efficient Ray Tracing Method for Terrain Rendering,” Pacific Graphics '95, August 1995.
Trobec et. al. discuss improvements in precision through bi-linear reconstruction along the directions, or in speed by using a Bresenham algorithm. See, Tomá{hacek over (s)}Trobec, Borut {hacek over (Z)}alik, and Nikola Guid, “Calculation of Visibility from Raster Relief Models,” 14th Spring Conference on Computer Graphics, Comenius University, Bratislava, Slovakia, Edited by LászlóSzirmay Kalos, pp. 257-266(April 1998), and earlier algorithms described by L. De Floriani, P. Magillo, “Algorithms for Visibility Computation on Digital Terrain Models,” Proceedings ACM Symposium on Applied Computing'93, Indianapolis, February 1993, and L. De Floriani, P. Magillo, “Computing Visibility Maps on a Digital Terrain Model, Spatial Information Theory—A Theoretical Basis for GIS,” A. U. Frank, I. Campari (Editors), Lecture Notes in Computer Science, N.7 16, Springer-Verlag, 1993, pp. 248-269. In general, many of the above algorithms are characterized as line-sweeping algorithms, because lines are explicitly and individually traced from the eye outward along selected directions.
Terrain visibility algorithms have been proposed. Visibility culling on a hierarchially represented terrain is described by Stewart. See, A. James Stewart, “Fast Horizon Computation at All Points of a Terrain With Visibility and Shading Applications,” IEEE Transactions on Visualization and Computer Graphics, 4(1), 1998, pp. 82-93, and A. James Stewart, “Hierarchical Visibility in Terrains,” Eurographics Rendering Workshop 1997, Springer Wien, Edited by Julie Dorsey and Philipp Slusallek, pp. 217-228. Characterization of several other terrain visibility algorithms can be found in L. De Floriani, P. Magillo, “Visibility Algorithms on Triangulated Digital Terrain Models,” International Journal of Geographic Information Systems, London, 8, 1, 1994, and Leila De Floriani and Paola Magillo, “Horizon computation on a hierarchical triangulated terrain model.,” The Visual Computer, 11(3), Springer-Verlag 1995, pp. 134-149. One approach determines a fuzzy visibility on terrain where a height value is represented as intervals instead of a single number. See, Livio Crocetta, Giovanni Gallo and Salvatore Spinello, “Visibility in Digital Terrain Maps: a Fuzzy Approach,” 14th Spring Conference on Computer Graphics, Comenius University, Bratislava, Slovakia, Edited by LászlóSzirmay Kalos, April 1998, pp. 257-266. Note that these algorithms compute a horizon map (in image or geometric form) to support the binary decision whether each point on the terrain is visible from the eye point. This is adequate only for determining whether a portion of the height field is occluded by other parts of the height field itself. The visibility and culling of other objects on the terrain (buildings, vehicles, trees, helicopters, etc.) is not accounted for in such a binary decision based on height field values. An actual minimum visible height at each height field point is not determined as in the present invention.
What is needed is an improved visibility algorithm for culling terrain data.